package main

import (
	"sort"
)

// 611. 有效三角形个数
func main() {
	println(triangleNumber([]int{4, 2, 3, 4}))
}

func triangleNumber(nums []int) int {
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] > nums[j]
	})
	count := 0
	for i := 0; i < len(nums)-2; i++ {
		count += findTow(nums[i+1:], nums[i])
	}
	return count
}

// 4 3 2 2

func findTow(nums []int, c int) int {
	i, j := 0, len(nums)-1
	count := 0
	for i < j {
		if nums[i]+nums[j] > c {
			count += j - i
			i++
		} else {
			j--
		}
	}
	return count
}
